package com.mccken.practice.data_structure.data_04;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-31 16:57
 **/
public class NextGreaterElement {

	public int[] nextGreaterElement(int[] nums1, int[] nums2) {

		int len1 = nums1.length;
		int len2 = nums2.length;

		// 辅助map，用于存储nums2中的下一个更大值
		HashMap<Integer, Integer> map = new HashMap<>();
		Stack<Integer> queue = new Stack<>();
		for (int i = len2 - 1; i >= 0; i--) {
			while (!queue.isEmpty() && queue.peek() < nums2[i]) {
				queue.pop();
			}

			int value = queue.isEmpty() ? -1 : queue.peek();
			map.put(nums2[i], value);
			queue.push(nums2[i]);
		}

		System.out.println(map.toString());

		int[] result = new int[len1];
		for (int i = 0; i < len1; i++) {
			result[i] = map.get(nums1[i]);

		}
		return result;
	}

	// 时间复杂度比较高了   时间复杂度为O(n^2)，空间复杂度为O(n)
	public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;

		int[] result = new int[len1];
		// base case
		if (len2 == 1) {
			result[0] = -1;
			return result;
		}

		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < len2; i++) {
			map.put(nums2[i], i);
		}

		for (int i = 0; i < len1; i++) {
			result[i] = -1;
			Integer nums2Index = map.get(nums1[i]);
			for (int j = nums2Index + 1; j < len2; j++) {
				if (nums2Index == len2 - 1) {
					result[i] = -1;
					break;
				}
				if (nums2[j] > nums1[i]) {
					result[i] = nums2[j];
					break;
				}
			}
		}

		return result;
	}

	public static void main(String[] args) {
		NextGreaterElement nextGreaterElement = new NextGreaterElement();
		int[] result1 = nextGreaterElement.nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2});
		System.out.println(Arrays.toString(result1));
//		int[] result2 = nextGreaterElement.nextGreaterElement(new int[]{2, 4}, new int[]{1, 2, 3, 4});
//		System.out.println(Arrays.toString(result2));
		int[] result3 = nextGreaterElement.nextGreaterElement(new int[]{1, 3, 5, 2, 4}, new int[]{6, 5, 4, 3, 2, 1, 7});
		System.out.println(Arrays.toString(result3));
	}

	public int[] nextGreaterElement(int[] nums) {
		int n = nums.length;
		int[] res = new int[n];

		Stack<Integer> stack = new Stack<>();
		// 假装这个数组长度翻倍了
		for (int i = 2 * n - 1; i >= 0; i--) {
			while (!stack.empty() && stack.peek() <= nums[i % n]) {
				stack.pop();
			}
			// 利用%求防止索引越界
			res[i % n] = stack.isEmpty() ? -1 : stack.peek();
			stack.push(nums[i % n]);
		}
		return res;
	}

}
